package main

import "fmt"

type ListNode struct {
	key   int
	value int
	pre   *ListNode
	next  *ListNode
}

type LRU struct {
	capacity  int
	size      int
	head      *ListNode
	tail      *ListNode
	hashTable map[int]*ListNode
}

type LRUer interface {
	Init(capacity_ int)
	Get(key int) (int, bool)
	Put(key, value int)
	updateToHead(node *ListNode)
	deleteTailNode()
	addToHead(key, value int)
}

func (e *LRU) Init(capacity_ int) {
	// 创建头结点和尾结点
	e.capacity = capacity_
	e.size = 0
	e.hashTable = make(map[int]*ListNode) // 必须有，否则就是错误的

	e.head = new(ListNode)
	e.tail = new(ListNode)

	e.head.next = e.tail
	e.tail.pre = e.head
}

func (e *LRU) Get(key int) (int, bool) {
	if res, ok := e.hashTable[key]; ok {
		return res.value, true
	}

	// 没有该元素
	return 0, false
}

func (e *LRU) Put(key, value int) {
	if res, ok := e.hashTable[key]; ok {
		if res.value != value {
			res.value = value
		}
		e.updateToHead(res)
		return
	}

	//不存在的情况

	if e.size < e.capacity {
		e.addToHead(key, value)
		e.size++
		return
	}

	// 容量已经满的情况
	e.deleteTailNode()
	e.addToHead(key, value)
}

func (e *LRU) updateToHead(node *ListNode) {
	node.pre = e.head
	node.next = e.head.next
	e.head.next.pre = node
	e.head.next = node
}
func (e *LRU) deleteTailNode() {
	var temp *ListNode = e.tail.pre
	delete(e.hashTable, temp.key)

	temp.pre.next = e.tail
	e.tail.pre = temp.pre
}
func (e *LRU) addToHead(key, value int) {
	var node *ListNode = new(ListNode)

	node.key = key
	node.value = value

	e.hashTable[key] = node
	e.updateToHead(node)
}

func main() {
	var lru LRU
	lru.Init(1)
	for i := 0; i < 5; i++ {
		lru.Put(i, i+3)
	}

	for i := 0; i < 5; i++ {
		if _, ok := lru.Get(i); ok {
			fmt.Println("success")
		} else {
			fmt.Println("no exist")
		}
	}
}
